package List

import (
	"fmt"
)

type List struct {
	array  []interface{}
	front  int
	back   int
	length int
}

func New(args ...int) *List {
	switch len(args) {
	case 1:
		return &List{make([]interface{}, args[0]), 0, 0, 0}
	}
	return &List{make([]interface{}, 8), 0, 0, 0}
}

func (list *List) Push(value interface{}) {
	if cap(list.array) == list.length {
		list.Resize(list.length*2 + 1)
	}
	if list.length == 0 {
		list.array[list.back] = value
		list.front = 0
		list.back = 0
	} else {
		if list.back == cap(list.array)-1 {
			list.back = 0
		} else {
			list.back++
		}
		list.array[list.back] = value
	}
	list.length++
}

func (list *List) Pop() interface{} {
	if list.length == 0 {
		panic("The queue is empty")
	}
	var value = list.array[list.back]
	if list.back == 0 {
		list.back = cap(list.array) - 1
		list.front = 0
		list.back = 0
	} else {
		list.back--
	}
	list.length--
	return value
}

func (list *List) Shift(value interface{}) {
	if cap(list.array) == list.length {
		list.Resize(list.length*2 + 1)
	}
	if list.length == 0 {
		list.array[list.front] = value
	} else {
		if list.front == 0 {
			list.front = cap(list.array) - 1
		} else {
			list.front--
		}
		list.array[list.front] = value
	}
	list.length++
}

func (list *List) UnShift() interface{} {
	if list.length == 0 {
		panic("The queue is empty")
	}
	var value = list.array[list.front]
	if list.front == cap(list.array)-1 {
		list.front = 0
	} else {
		list.front++
	}
	list.length--
	return value
}

func (list *List) Resize(length int) {
	var array = make([]interface{}, length)
	for i := 0; i < list.length; i++ {
		array[i] = list.Get(i)
	}
	list.front = 0
	list.back = len(list.array) - 1
	list.array = array
}

func (list *List) Set(index int, value interface{}) {
	if index >= list.length || index < 0 {
		panic(fmt.Sprint("runtime error: index out of range [", index, "] with length ", list.length))
	}
	if list.back >= list.front {
		list.array[list.front+index] = value
	} else {
		if index+list.front >= cap(list.array) {
			list.array[index-cap(list.array)+list.front] = value
		} else {
			list.array[index+list.front] = value
		}
	}
}

func (list *List) Insert(index int, value interface{}) {
	if cap(list.array) == list.length {
		list.Resize(list.length*2 + 1)
	}
	if index*2 > list.length {
		list.Push(value)
		for i := list.length - 1; i != index; i-- {
			list.Set(i, list.Get(i-1))
		}
		list.Set(list.length-1, value)
	} else {
		list.Shift(value)
		for i := 0; i != index; i++ {
			list.Set(i, list.Get(i+1))
		}
		list.Set(0, value)
	}
}

func (list *List) Remove(index int) {
	if index >= list.length || index < 0 {
		panic(fmt.Sprint("runtime error: index out of range [", index, "] with length ", list.length))
	}
	if index*2 > list.length {
		for i := index; i < list.length; i++ {
			list.Set(i, list.Get(i+1))
		}
		list.Pop()
	} else {
		for i := index; i > 0; i-- {
			list.Set(i, list.Get(i-1))
		}
		list.UnShift()
	}
}

func (list *List) Swap(i int, j int) {
	if i >= list.length || i < 0 || j >= list.length || j < 0 {
		panic(fmt.Sprint("runtime error: index out of range [", i, ",", j, "] with length ", list.length))
	}
	var t = list.Get(i)
	list.Set(i, list.Get(j))
	list.Set(j, t)
}

func (list *List) Get(index int) interface{} {
	if index > list.length || index < 0 {
		panic(fmt.Sprint("runtime error: index out of range [", index, "] with length ", list.length))
	}
	if list.back > list.front {
		return list.array[list.front+index]
	} else {
		if index+list.front >= cap(list.array) {
			return list.array[index-cap(list.array)+list.front]
		}
		return list.array[index+list.front]
	}
}

func (list *List) Front() interface{} {
	if list.length > 0 {
		return list.array[list.front]
	}
	return nil
}

func (list *List) Back() interface{} {
	if list.length > 0 {
		return list.array[list.back]
	}
	return nil
}

func (list *List) Fill(value interface{}) {
	for i := 0; i < cap(list.array); i++ {
		list.array[i] = value
	}
	list.front = 0
	list.back = 0
	list.length = cap(list.array)
}

func (list *List) Clear() {
	list.array = make([]interface{}, 8)
	list.front = 0
	list.back = 0
	list.length = 0
}

func (list *List) Len() int {
	return list.length
}

func (list *List) Cap() int {
	return cap(list.array)
}
